import java.util.*;

class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
 }

public class Test {
    // 相同的树
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null){
            return true;
        }
        if(p == null || q == null || p.val != q.val ){
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

    // 对称二叉树：
    public boolean isSymmetric(TreeNode root) {
        return isSameTree1(root.left, root.right);
    }
    public boolean isSameTree1(TreeNode p, TreeNode q){
        if(p == null && q == null){
            return true;
        }
        if(p == null || q == null || p.val != q.val){
            return false;
        }
        return isSameTree1(p.left, q.right) && isSameTree1(p.right, q.left);
    }

    // 二叉树的最大深度
    public int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);

        return Math.max(left, right) + 1;
    }

    // 翻转二叉树 ♥
    public TreeNode invertTree1(TreeNode root) {
        if(root == null){
            return root;
        }
        TreeNode temp = root.left;
        root.left = invertTree1(root.right);
        root.right = invertTree1(temp);

        return root;
    }

    public TreeNode invertTree(TreeNode root) {
        if(root == null){
            return root;
        }
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);

        root.left = right;
        root.right = left;

        return root;
    }

    // 不同的二叉搜索树
    public int numTrees(int n) {
        int[] G = new int[n + 1];
        G[0] = G[1] = 1;
        for(int i = 2; i <= n; i++){
            for(int j = 1; j <= i; j++){
                G[i] += G[j - 1] * G[i - j];
            }
        }
        return G[n];
    }

    // 不同的二叉搜索树 II ♥
    public List<TreeNode> generateTrees(int n) {
        return generateTrees(1, n);
    }

    public List<TreeNode> generateTrees(int start, int end) {
        List<TreeNode> list = new LinkedList<>();
        if(start > end){
            list.add(null);
            return list;
        }
        for(int i = start; i <= end; i++){
            List<TreeNode> leftNode = generateTrees(start, i - 1);
            List<TreeNode> rigthNode = generateTrees(i + 1, end);
            for(TreeNode left : leftNode){
                for(TreeNode right : rigthNode){
                    TreeNode node = new TreeNode(i);
                    node.left = left;
                    node.right = right;
                    list.add(node);
                }
            }
        }
        return list;
    }

    // 路径总和
    public boolean hasPathSum(TreeNode root, int target) {
        if(root == null){
            return false;
        }
        if(root.left == null && root.right == null){
            return root.val == target;
        }
        int tar = target - root.val;
        return hasPathSum(root.left, tar) || hasPathSum(root.right, tar);
    }

    // 路径总合Ⅱ
    List<List<Integer>> list = new LinkedList<>();
    Deque<Integer> queue = new LinkedList<>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        dsf(root, target);
        return list;
    }

    public void dsf(TreeNode root, int target){
        if(root == null){
            return;
        }
        queue.offer(root.val);
        if(root.left == null && root.right == null && root.val == target){
            list.add(new LinkedList<>(queue));
        }
        int tar = target - root.val;
        dsf(root.left, tar);
        dsf(root.right, tar);
        queue.pollLast();
    }

    // 二叉树的所有路径
    // 震惊！队列可以遍历。
    List<String> list1 = new LinkedList<>();
    Deque<String> queue1 = new LinkedList<>();
    public List<String> binaryTreePaths(TreeNode root) {
        dsf1(root);
        return list1;
    }

    public void dsf1(TreeNode root){
        if(root == null){
            return;
        }
        queue1.offer(root.val + "");
        if(root.left == null && root.right == null ){
            StringBuilder stringBuilder = new StringBuilder();
            for(String s : queue1){
                stringBuilder.append(s+"->");
            }
            int len = stringBuilder.length();
            stringBuilder.delete(len - 2, len);
            list1.add(stringBuilder.toString());
        }

        dsf1(root.left);
        dsf1(root.right);
        queue.pollLast();
    }

    // 验证二叉搜索树
    int flag = 1;
    TreeNode pre = null;
    public boolean isValidBST(TreeNode root) {
        inorder(root);
        return flag == 1;
    }

    public void inorder(TreeNode root){
        if(root == null){
            return;
        }
        inorder(root.left);

        if(pre != null && pre.val >= root.val){
            flag = -1;
        }
        pre = root;
        inorder(root.right);
    }

    // 二叉树的最小深度
    public int minDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        int left = minDepth(root.left);
        int right = minDepth(root.right);

        return (left == 0 || right == 0) ? right + left + 1 : Math.min(right , left) + 1;
    }

    //平衡二叉树
    public boolean isBalanced(TreeNode root) {
        return height( root) >= 0;
    }

    public int height(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = height(root.left);
        if(left < 0){
            return -1;
        }
        int right = height(root.right);
        if(right < 0){
            return -1;
        }
        if(Math.abs(left - right) > 1){
            return -1;
        }else{
            return Math.max(left, right) + 1;
        }


    }








}
